package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2022/3/17 12:30
 * @description：https://leetcode-cn.com/problems/longest-word-in-dictionary/
 */
public class 词典中最长的单词 {
    @Test
    public void test() {
        Solution solution = new Solution();
    }


    class Trie {
        boolean isEnd;
        Trie[] children;

        public Trie() {
            this.isEnd = false;
            this.children = new Trie[26];
        }

        public void insert(String word) {
            Trie node = this;
            for (char ch : word.toCharArray()) {
                ch -= 'a';
                if (node.children[ch] == null) {
                    node.children[ch] = new Trie();
                }
                node = node.children[ch];
            }
            node.isEnd = true;
        }

        public boolean search(String word) {
            Trie node = this;
            for (char ch : word.toCharArray()) {
                ch -= 'a';
                if (node.children[ch] == null || !node.children[ch].isEnd) {
                    return false;
                }
                node = node.children[ch];
            }
            return true;
        }

    }

    class Solution {
        public String longestWord(String[] words) {
            Trie trie = new Trie();
            for (String word : words) {
                trie.insert(word);
            }
            String maxStr = "";
            for (String word : words) {
                if (trie.search(word)) {
                    if (word.length() > maxStr.length() || (word.length() == maxStr.length() && word.compareTo(maxStr) < 0)) {
                        maxStr = word;
                    }
                }
            }
            return maxStr;
        }
    }
}
